package danran.dp;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @Classname DP
 * @Description TODO
 * @Date 2021/11/26 17:37
 * @Created by ASUS
 */
public class DP {

    static class MinimumTotal {

        public int minimumTotal(List<List<Integer>> triangle) {
            for (int i = triangle.size() - 1; i >= 1; i--) {
                List<Integer> cur = triangle.get(i);
                List<Integer> up = triangle.get(i - 1);
                for (int j = 0; j < cur.size() - 1; j++) {
                    up.set(j, Math.min(cur.get(j), cur.get(j + 1)) + up.get(j));
                }
            }
            return triangle.get(0).get(0);
        }

    }

    public boolean wordBreak_failed(String s, List<String> wordDict) {
        List<String> dict = wordDict.stream().sorted(Comparator.comparing(String::length)).collect(Collectors.toList());
        for (String str : dict) {
            String[] split = s.split(str);
            if (split.length == 0) return true;
            else s = concatString(split);
        }
        return false;
    }

    private String concatString(String[] array) {
        StringBuilder builder = new StringBuilder();
        for (String s : array) {
            builder.append(s);
        }
        return builder.toString();
    }

    public boolean wordBreak(String s, List<String> dict) {
        boolean[] dp = new boolean[s.length() + 1];
        Arrays.fill(dp, false);
        dp[0] = true;
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j <= i; j++) {
                if (dp[j] && dict.contains(s.substring(j, i + 1))) {
                    dp[i + 1] = true;
                    break;
                }
            }
        }
        return dp[dp.length - 1];
    }

    static class GenerateParenthesis {
        List<String> res = new ArrayList<>();

        public List<String> generateParenthesis(int n) {
            if (n <= 0) {
                return res;
            }
            getParenthesis("", n, n);
            return res;
        }

        private void getParenthesis(String str, int left, int right) {
            if (left == 0 && right == 0) {
                res.add(str);
                return;
            }
            if (left == right) {
                //剩余左右括号数相等，下一个只能用左括号
                getParenthesis(str + "(", left - 1, right);
            } else if (left < right) {
                //剩余左括号小于右括号，下一个可以用左括号也可以用右括号
                if (left > 0) {
                    getParenthesis(str + "(", left - 1, right);
                }
                getParenthesis(str + ")", left, right - 1);
            }
        }
    }

    public int maxProduct(int[] nums) {
        int[] dp_max = new int[nums.length + 1];
        int[] dp_min = new int[nums.length + 1];
        if (nums.length == 0) return 0;
        int max = Integer.MIN_VALUE;
        // 由于存在负数，所以需要维护两个数组
        // dp_max[i] 指的是以第 i 个数结尾的 乘积最大 的连续子序列
        // dp_min[i] 指的是以第 i 个数结尾的 乘积最小 的连续子序列
        dp_max[0] = 1;
        dp_min[0] = 1;
        for (int i = 1; i <= nums.length; i++) {
            // 如果数组的数是负数，那么会导致 max 变成 min，min 变成 max
            // 故需要交换dp
            if (nums[i - 1] < 0) {
                int temp = dp_min[i - 1];
                dp_min[i - 1] = dp_max[i - 1];
                dp_max[i - 1] = temp;
            }
            dp_min[i] = Math.min(nums[i - 1], dp_min[i - 1] * nums[i - 1]);
            dp_max[i] = Math.max(nums[i - 1], dp_max[i - 1] * nums[i - 1]);
            max = Math.max(max, dp_max[i]);
        }
        return max;
    }

    public static void main(String[] args) {
        /*"cars"
["car","ca","rs"]
"catsandog"
["cats","dog","sand","and","cat"]
*/
        System.out.println(new DP().maxProduct(new int[]{-2, 0, -1}));
    }
}
